Computer program listing appendices are submitted herewith on one compact disc and one duplicate compact disc. The total number of compact discs including duplicates is two. The files on the compact disc are ASCII text files in which the characters are displayed as their corresponding values in hexadecimal format. Their names, dates of creation, directory locations, and sizes in bytes are:
1. Directory appndxI containing file 36725aI.HEX (Appendix I) of Jan. 16, 2001 and of length 55,519 bytes.
2. Directory appndxII containing file 36725aII.HEX (Appendix II) of Jan. 16, 2001 and of length 8,260 bytes.
The files are referred to herein as appendices I and II respectively. The material on the compact discs is incorporated by reference herein.
The present invention relates generally, to positioning systems and more particularly to positioning systems employing alternating electromagnetic fields and acceleration measurements, as well as to an apparatus for localization and tracking using an extended Kalman filter.
Various types of positioning systems which employ alternating electromagnetic fields are known. The following U.S. Patents and foreign patent documents are believed to represent the state of the art for positioning systems:
U.S. Pat. Nos. 4,054,881 and 4,314,251 to Raab; U.S. Pat. Nos. 4,622,644, 4,642,786, 5,742,394, 5,744,953, 5,767,669, 5,831,260 and 5,953,683 to Hansen; U.S. Pat. No. 4,737,794 to Jones; U.S. Pat. Nos. 4,613,866, 4,945,305 and 4,849,692 to Blood; U.S. Pat. Nos. 3,868,565, 3,983,474, 4,017,858, 4,298,874 and 4,742,356 to Kuipers; U.S. Pat. Nos. 5,168,222 and 5,172,056 to Volsin et al; U.S. Pat. No. 5,0170,172 to Weinstein; U.S. Pat. Nos. 5,453,686 and 5,640,170 to Anderson; U.S. Pat. No. 5,767,960 to Orman; U.S. Pat. No. 5,600,330 to Blood; U.S. Pat. No. 5,307,072 to Jones; U.S. Pat. No. 4,710,708 to Rorden; U.S. Pat. No. 4,346,384 to Raab; U.S. Pat. No. 4,328,548 to Crow; U.S. Pat. No. 5,558,091 to Acker; U.S. Pat. No. 5,592,939 to Martinelli; U.S. Pat. No. 6,073,043 to Schnieder; U.S. Pat. No. 3,644,825 to Davis; U.S. Pat. No. 5,377,678 to Dumoulin; U.S. Pat. Nos. 4,287,809 and 4,394,831 to Egli; U.S. Pat. No. 4,396,885 to Constant WO 96/05768 to Ben-Haim and WO 94/04938 to Bladen;
U.S. Pat. No. 4,710,708 to Rorden describes a positioning system which employs only one electromagnetic coil.
A description of accelerometer technology may be found in Capacitive Sensors, L. K. Baxter, 1998 ISBN 0-7803-5351-X;
U.S. Pat. No. 5,592,401 to Kramer, U.S. Pat. No. 5,657,226 to Shin, U.S. Pat. No. 5,615,116 to Gudat, U.S. Pat. No. 5,615,132 to Horton, U.S. Pat. No. 5,956,250 to Gudat, U.S. Pat. No. 5,902,351 to Streit, U.S. Pat. No. 5,991,692 to Spencer, U.S. Pat. No. 4,506,979 to Rogers, U.S. Pat. No. 5,051,751 to Gray and U.S. Pat. No. 5,930,741 to Kramer, all describe positioning systems which may employ Kalman filtering and acceleration measurements.
Phase Locked Loop technology is described in xe2x80x9cPhase locked loop: simulation and applicationsxe2x80x9d, by Roland E. Best, McGraw-Hill Book Company, ISBN 0070060517.
The theory of non-linear filtering and its applications is discussed in:
H. J. Kushner, xe2x80x9cApproximations to Optimal Nonlinear Filtersxe2x80x9d. IEEE Trans. A.C., Vol. AC-12, No. 5, October 1967;
A. Gelb, J. F. Kaspar, Jr., R. A. Nash, Jr., C. E. Price, and A. A. Southerland, Jr., xe2x80x9cApplied Optimal Estimationxe2x80x9d, M.I.T. Press, Cambridge, Mass., 1974;
B. D. O. Anderson, and J. B. Moore, xe2x80x9cOptimal Filteringxe2x80x9d, Prentice-Hall, Englewood Cliffs, N.J., 1979;
A. H. Jazwinski, xe2x80x9cStochastic Processes and Filtering Theoryxe2x80x9d, Academic Press, New York, 1971; and
M. S. Grewal, and A. P. Andrews, xe2x80x9cKalman Filteringxe2x80x9d, Prentice-Hall, Upper Saddle River, N.J., 1993.
The Electromagnetic field equation laws are discussed in:
J. D. Jackson, xe2x80x9cClassical Electrodynamicsxe2x80x9d, John Wiley and Sons, New York, New York, 1975.
The application of Extended Kalman filters (EKF) to tracking in the context of radar is discussed, for example, in U.S. Pat. Nos. 5,075,694, 4,179,696, 3,952,304 and 3,935,572. Other tracking systems are discussed, for example, in U.S. Pat. Nos. 5,095,467 and 4,855,932.
The Kalman filter is a standard tool for xe2x80x9cdata fusionxe2x80x9d of different sensors. In U.S. Pat. No. 5,416,712, Global Positioning System (GPS) signals and dead reckoning are combined by a Kalman filter, where the gyro bias is also calibrated. In U.S. Pat. No. 5,645,077 automatic drift compensation is discussed.
Reference is also made to positioning and tracking systems described in the following U.S. patent and patent applications assigned to the assignee of the present invention, which are herein incorporated each in its entirety, by reference. U.S. Pat. No. 6,141,293 to Moriya at el.; U.S. patent application Ser. No. 09/345,189 entitled xe2x80x9cA system and method for three dimensional positioning and trackingxe2x80x9d, filed on Jun. 30, 1999 to Moriya and Itzkovich; U.S. patent application Ser. No. 09/384,314 entitled xe2x80x9cA localization and tracking systemxe2x80x9d, filed on Aug. 27, 1999 to Moriya and Albeck; and U.S. patent application Ser. No. 09/503,436 entitled xe2x80x9cA system for three dimensional positioning and tracking with dynamic range extensionxe2x80x9d, filed on Feb. 14, 2000 to Moriya.
The disclosures of all publications mentioned in the specification are hereby incorporated in their entirety by reference.
Preferred embodiments of the present invention provide an improved apparatus and method for positioning and tracking objects, particularly using a non-linear Kalman Filter tracker, where electromagnetic field data and acceleration information are used simultaneously for the determination of the position and orientation of a remote sensing device.
An acceleration measuring device is typically used to provide acceleration information of the moving object. A particular advantage of a preferred embodiment of the present invention is the fusion of the acceleration information in the tracking in order to increase the location, i.e. position and orientation, accuracy.
In a preferred embodiment of the present invention, the axial rotation of a probe sensor around at least one direction in space can be monitored.
Preferably, a periodic comparison between the position data based on electromagnetic field information and both electromagnetic and acceleration data is obtained. The results of the comparison is then used in order to indicate electromagnetic disturbances in the operating environment.
Preferably, a system constructed and operative in accordance with a preferred embodiment of the present invention comprises N transmitters and M receiving elements in the probe sensor which detects at least 6 electromagnetic signals, each of the transmitters is characterized by its own frequency and at least one linear multi-axial acceleration detector which detects the actual acceleration components in the direction perpendicular to its prime axis that are connected to a digital signal processing circuit. The analog output of the electromagnetic signal detector is a voltage signal proportional to the superposition of the N electromagnetic field transmitters at the coordinates xi, yi, zi xcfx86I, xcex8i, and "psgr" where the index i denotes the position of the electromagnetic source i. The output of the acceleration detecting components are voltage signals which are functions of the actual acceleration components in the direction perpendicular to its prime axis.
It is a particular feature of a preferred embodiment of the present invention that the antenna coils need not be exactly mutually orthogonal and certainly need not be arranged such that the centers of the antenna coils coincide.
Preferably, analog signals of both electromagnetic field detectors and the acceleration components are digitized and are introduced to an integrated digital signal processor block, as an input data. The digitized input data from the sensor is then used by a digital signal processor, to compute the position and orientation coordinates of the sensor. The output from the digital signal processor is transferred to a data communication unit and then to a system control unit. The refresh rate of the output data is typically of the order of few times per second to a few hundred times per second.
The detector may comprise a multi-axial acceleration detector and at least one-axis antenna coil, and may alternatively comprise any other suitable type of one-axis electromagnetic field detector, such as a Hall-effect detector or a solid state component, e.g., a magneto-resistive detector or a magneto-diode or a magneto-transistor. The digital signal processor typically comprises two modules: an envelope detector module and a position determination unit.
The Envelope Detector (hereafter referred as xe2x80x9cEDxe2x80x9d), is operative to determine the received envelope amplitudes (magnitude and sign) C1, . . . , CN of the N electromagnetic signals received from the N Electromagnetic field transmitters. The ED is typically comprised of N identical envelope detectors working in parallel. Each of the ED modules preferably comprises two sub-modules: a phase lock loop (hereafter PLL), and a system synchronization unit, which is operative during the operation of the ED module to define the absolute sign of the signal amplitude. Alternatively, each ED module may comprise three sub-modules operating in parallel and another sub-module that is invoked when system synchronization is needed. The three modules are: a phase lock loop, a non-coherent absolute value envelope-detector, and a sign detection unit. A fourth sub-module, system synchronization unit, may be invoked to define the absolute sign of the signal amplitude.
The output of the envelope detector is supplied to a position determination unit which is operative, based on the signed amplitude values supplied by the envelope detector, to provide an output indication of the position of the electromagnetic field detector in the sensor.
There is thus provided in accordance with a preferred embodiment of the present invention a system for tracking and positioning a moving object, the system including a plurality of transmitters operative to transmit alternating electromagnetic fields within a three-dimensional space, and at least one sensor arranged to be fixed to at least one corresponding portion of a moving object whose position it is sought to monitor, each of the at least one sensors including an electromagnetic field receiver having at least one active axis and operative to receive at least one component, lying along the at least one active axis respectively, of the alternating electromagnetic fields, an accelerometer to independently measure at least one component of the acceleration of the moving object, and a digital signal processor adapted to store at least one characteristic of the electromagnetic fields as received by the electromagnetic field receiver, and at least one characteristic of the acceleration as measured by the accelerometer, and to transmit the stored characteristics to a Kalman filter, and to compute therefrom an estimate of at least one component of the position and orientation of the moving object.
Also in accordance with a preferred embodiment of the present invention the Kalman filter employs at least one estimate of an acceleration value""s components in order to compute an estimate of the at least one component of the moving object""s position and orientation and wherein the Kalman filter employs the at least one independently measured component of the acceleration of the moving object as the at least one estimated acceleration value""s components, rather then deriving the at least one estimated acceleration value""s components from the electromagnetic field information.
There is further provided in accordance with another preferred embodiment of the present invention a system for indicating a disturbance in an electromagnetic field, the system including a plurality of transmitters operative to transmit alternating electromagnetic fields within a three-dimensional space, and at least one sensor arranged to be fixed to at least one corresponding portion of a moving object whose position it is sought to monitor. Each of the at least one sensors includes an electromagnetic field receiver having at least one active axis and operative to receive at least one component, lying along the at least one active axis respectively, of the alternating electromagnetic fields, an accelerometer operative to independently measure at least one component of the acceleration of the moving object, and a digital signal processor for storing at least one characteristic of the electromagnetic fields as received by the electromagnetic field receiver, and at least one characteristic of the acceleration as measured by the accelerometer. The digital signal processor is adapted to transmit the at least one stored characteristic of the electromagnetic fields to a Kalman filter and calculate therefrom a first estimate of at least one component of the position and orientation of the moving object, transmit the at least one stored characteristics of the electromagnetic field and the at least one characteristic of the acceleration as measured by the accelerometer to the Kalman filter, and calculate therefrom a second estimate of at least one component of the position and orientation of the moving object, and compare the first and second estimates for a discrepancy indicating a disturbance in the electromagnetic field.
Further in accordance with a preferred embodiment of the present invention the digital signal processor compares the first and second estimates for a discrepancy indicating a disturbance in the electromagnetic field on a periodic basis.
Also in accordance with a preferred embodiment of the present invention, the Kalman filter calculating the second estimate of at least one component of the position and orientation of the moving object employs at least one estimate of an acceleration value""s components in order to compute an estimate of the at least one component of the moving object""s location and the Kalman filter employs the at least one independently measured component of the acceleration of the moving object as the at least one estimated acceleration value""s components, rather then deriving the at least one estimated acceleration value""s components from the electromagnetic field information.
There is further provided in accordance with another preferred embodiment of the present invention a method for tracking and positioning a moving object, the method including positioning a plurality of transmitters operative to transmit alternating electromagnetic fields within a three-dimensional space, affixing at least one sensor to at least one corresponding portion of the moving object whose position it is sought to monitor, each of the at least one sensors including an electromagnetic field receiver having at least one active axis and operative to receive at least one component, lying along the at least one active axis respectively, of the alternating electromagnetic fields, and an accelerometer operative to independently measure at least one component of the acceleration of the moving object, and storing at least one characteristic of the electromagnetic fields as received by the electromagnetic field receiver, and at least one characteristic of the acceleration as measured by the accelerometer, transmitting the stored characteristics to a Kalman filter, and computing therefrom an estimate of at least one component of the position and orientation of the moving object.
Still further in accordance with a preferred embodiment of the present invention the method includes employing at least one estimate of an acceleration value""s components in order to compute an estimate of the at least one component of the moving object""s position and orientation wherein the at least one independently measured component of the acceleration of the moving object is employed as the at least one estimated acceleration value""s components, rather than deriving the at least one estimated acceleration value""s components from the electromagnetic field information.
There is also provided in accordance with another preferred embodiment of the present invention a method for indicating a disturbance in an electromagnetic field, the method including positioning a plurality of transmitters operative to transmit alternating electromagnetic fields within a three-dimensional space, and affixing at least one sensor to at least one corresponding portion of a moving object whose position it is sought to monitor, each of the at least one sensors comprising an electromagnetic field receiver having at least one active axis and operative to receive at least one component, lying along the at least one active axis respectively, of the alternating electromagnetic fields, and an accelerometer operative to independently measure at least one component of the acceleration of the moving object, storing at least one characteristic of the electromagnetic fields as received by the electromagnetic field receiver, and at least one characteristic of the acceleration as measured by the accelerometer, transmitting the at least one stored characteristic of the electromagnetic fields to a Kalman filter and calculating therefrom a first estimate of at least one component of the position and orientation of the moving object, transmitting the at least one stored characteristics of the electromagnetic field and the at least one characteristic of the acceleration as measured by the accelerometer to the Kalman filter, and calculating therefrom a second estimate of at least one component of the position and orientation of the moving object, and comparing the first and second estimates for a discrepancy indicating a disturbance in the electromagnetic field.
Still further in accordance with a preferred embodiment of the present invention comparing first and second estimates for a discrepancy indicating a disturbance in the electromagnetic field occurs on a periodic basis.
Additionally in accordance with a preferred embodiment of the present invention a discrepancy indicating a disturbance in the electromagnetic field comprises a discrepancy of greater than the expected absolute accuracy of the measurement of the position and orientation of the moving object.
Further in accordance with a preferred embodiment of the present invention at least one component of the position of the moving object comprises at least two components.
Still further in accordance with a preferred embodiment of the present invention at least two components of the position of the moving object comprises three components.
Additionally in accordance with a preferred embodiment of the present invention at least one component of the position of the moving object is selected from the group consisting of the x, y, and z coordinates of the moving object.
Further in accordance with a preferred embodiment of the present invention at least one component of the acceleration of the moving object comprises at least two components.
Still further in accordance with a preferred embodiment of the present invention at least two components of the acceleration of the moving object comprises three components.
Additionally in accordance with a preferred embodiment of the present invention at least one component of the acceleration of the moving object is selected from the group consisting of the ax, ay, and az acceleration components of the moving object.
Still further in accordance with a preferred embodiment of the present invention calculating the second estimate of at least one component of the position and orientation of the moving object comprises employing at least one estimate of an acceleration value""s components in order to compute an estimate of the at least one component of the moving object""s location, and employing the at least one independently measured component of the acceleration of the moving object as the at least one estimated acceleration value""s components, rather then deriving the at least one estimated acceleration value""s components from the electromagnetic field information.
Additionally in accordance with a preferred embodiment of the present invention employing the at least one independently measured component of the acceleration of the moving object as the at least one estimated acceleration value""s components improves the accuracy of the estimate of the at least one component of the position and orientation of the moving object.
Also in accordance with a preferred embodiment of the present invention the electromagnetic field receiver comprises a single axis electromagnetic field receiver, with the accelerometer is attached thereto, such that employing the at least one independently measured component of the acceleration of the moving object as the at least one estimated acceleration value""s components provides information about the axial rotation of the moving object.
There is further provided in accordance with a preferred embodiment of the present invention a system for monitoring of the position of at least one portion of an object, the system including at least one positioning sensors arranged to be fixed to at least one corresponding portion of the object whose positions it is sought to monitor, each of the at least one positioning sensors including an acceleration detector having at least one active direction lying along the at least one active axes of the direction of movement, and at least one digital signal processors for storing at least one characteristic of the acceleration component.
It is a particular feature of a preferred embodiment of the present invention that at least one acceleration detecting component is used to detect the acceleration of at least one acceleration component of at least one sensor for at least one portion of the time.
Still further in accordance with a preferred embodiment of the present invention the acceleration detector has at least a single (detection) active axis and is operative to receive the component of the acceleration measurements along the single (detection) active axis.
There is also provided in accordance with another preferred embodiment of the present invention a system for monitoring the position of at least one portions of an object in three-dimensional space having three axes, the system including a plurality of electromagnetic transmitters each having a center and each operative to transmit alternating electromagnetic fields within a three-dimensional space, a transmitter orientation maintainer operative to maintain at least three of the transmitters in orientations such that at least a component of the electromagnetic field of at least one of the transmitters falls within each of the 3 axes of the 3-dimensional space, and wherein less than all of the centers of the transmitters coincide, at least one positioning sensors arranged to be fixed to at least one corresponding portions of the object whose positions it is sought to monitor, each of the at least one positioning sensors comprising an electromagnetic field receiver receiving the alternating electromagnetic fields from the plurality of transmitters, and at least one accelerometer detector with at least one active direction, and at least one digital signal processor for storing at least one characteristic of the electromagnetic fields as transmitted by the plurality of transmitters and comparing the at least one characteristic to at least one characteristic of the electromagnetic fields as received by at least a corresponding one of the at least one positioning sensors and, at least one component of the acceleration of the movement of the sensor in the direction of at least one axis and, accordingly, determining at least one position characteristic of at least one object portion.
Still further in accordance with a preferred embodiment of the present invention the at least one acceleration detector is provided integrally with a corresponding one of the at least one positioning sensors.
There is also provided in accordance with yet another preferred embodiment of the present invention a system for monitoring the position of at least one portions of an object in three-dimensional space having three axes, the system including a plurality of electromagnetic transmitters each having an active axial direction and each operative to transmit alternating electromagnetic fields within a three-dimensional space, a transmitter orientation maintainer operative to maintain at least three of the transmitters in orientations such that at least a component of the electromagnetic field of at least one of the transmitters falls within each of the 3 axes of the 3-dimensional space, and wherein less than all of the transmitters"" active axial directions are mutually orthogonal, at least one positioning sensors arranged to be fixed to at least one corresponding portions of the object whose positions it is sought to monitor, each of the at least one positioning sensors comprising an electromagnetic field receiver receiving the alternating electromagnetic fields from the plurality of transmitters and, at least one component of the acceleration of the movement of the sensor in the direction of at least one axis and at least one digital signal processor for storing at least one characteristic of the electromagnetic fields as transmitted by the plurality of transmitters and comparing the at least one characteristic to at least one characteristic of the electromagnetic fields and at least one component of the acceleration measured by the accelerometer as received by at least a corresponding one of the at least one positioning sensors and, accordingly, determining at least one position characteristic of at least one object portion.
Still additionally in accordance with a preferred embodiment of the present invention at least one of the at least one digital signal processors, illustrated in FIG. 9, is operative to simultaneously process acceleration characteristics arriving from at least one of the plurality of the accelerometer components.
There is also provided in accordance with a preferred embodiment of the present invention a method for monitoring of the position of at least one portion of an object, the method includes affixing at least one positioning sensor to at least one corresponding portion of the object whose positions it is sought to monitor, the sensors being operative to receive alternating electromagnetic fields existing within a three dimensional space containing the object, comparing at least one characteristic of the electromagnetic fields as transmitted to at least one characteristic of the electromagnetic fields as received by the sensors and at least one component of the acceleration of the sensor during it movements in at least one spatial axis.
There is also provided in accordance with a preferred embodiment of the present invention a method for improving the accuracy of the position of at least one portions of an object, the method including affixing at least one positioning sensors arranged to be fixed to at least one corresponding portions of the object whose positions it is sought to monitor, each of the at least one positioning sensors comprising at least one acceleration detector having at least one active axes and operative to receive at least one component, lying along the at least one active axes respectively, of the direction of movement and, accordingly, use the data to increase the degree of accuracy of the positioning and orientation of at least on sensor attached to at least one portions of an object.
There is also provided in accordance with a preferred embodiment of the present invention a method for comparing the position and orientation results obtained with the electromagnetic fields detection components and the combined information of both the electromagnetic field detector and the acceleration detector of at least one sensor, and indication of inconsistency between the two results to monitor possible electromagnetic disturbances in the sensor""s environment.
There is thus further provided in accordance with yet another preferred embodiment of the present invention position and orientation tracking apparatus operative to track the position and orientation of a moving object based on electromagnetic flux measurements taken in the vicinity of the moving object and possibly acceleration measurements, the position and orientation tracking apparatus including a non-linear Kalman filter-based tracker operative to receive electromagnetic flux measurements performed in the vicinity of the moving object and possibly acceleration measurements thereof, to operate a non-linear Kalman-type filter on the measurements, thereby to generate information regarding the position and orientation of the moving object, and a position and orientation indicator operative to provide an output indication of the information regarding the position and orientation of the moving object.
The acceleration measures can be performed by 1-, 2- or 3-axis accelerometers, or by two 2-axis, or combinations thereof. The accelerometers can be laid on-center of the electromagnetic sensor or off-center, or in combinations thereof.
Further in accordance with a preferred embodiment of the present invention the position and orientation coordinates include 3 spatial coordinates and 3 orientation coordinates. The spin angle "psgr" is determined by the EKF by fusing the measurement data coming from the magnetic fluxes and the accelerometers.
Further in accordance with a preferred embodiment of the present invention the acceleration measurements are performed in the moving frame of the sensor, and when fused with the electromagnetic measurements by the EKF it enables the extraction of the full orientation.
Further in accordance with a preferred embodiment of the present invention the acceleration measurements increase the precision of the position and orientation measurements by fusing them with the electromagnetic measurements by the EKF.
Further in accordance with a preferred embodiment of the present invention the acceleration measurements eliminate or reduce the effect of passive magnetic scattering field, which otherwise degrade the performance of the system considerably.